package pers.qianyu.month_202011.date_20201124;

/**
 * 92. 反转链表 II
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 *
 * @author mizzle rain
 * @date 2020-11-24 11:10
 */
public class ReverseBetween {
    private ListNode lastNode;

    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == 1) {
            return solve(head, n);
        }
        head.next = reverseBetween(head.next, m - 1, n - 1);
        return head;
    }

    private ListNode solve(ListNode head, int n) {
        if (n == 1) {
            lastNode = head.next;
            return head;
        }
        ListNode last = solve(head.next, n - 1);
        head.next.next = head;
        head.next = lastNode;
        return last;
    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
